package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

/**
 * @author: lynn
 * @Descript: 全排列  https://www.bilibili.com/video/BV197411x7DP?from=search&seid=10919691241028760370
 * @date: 2021/5/10 23:03
 * @version: 1.0
 */
public class Q27_1_Permutation {

    TreeSet<String> result=new TreeSet<>();
    public ArrayList<String> Permutation(String str){
        if (str==null||str.length()<1){
            return new ArrayList<>();
        }
        List<Character> chars=new ArrayList<>();
        result=new TreeSet<>();//去重
        for (char c:str.toCharArray()) chars.add(c);//把字符串转成list
        Compose(chars,new StringBuffer(),str.length(),0);
        return new ArrayList<>(result);
    }
    private void Compose(List<Character> arr,StringBuffer buffer,int len,int index){
        if (index==len){ //递归结束条件
            result.add(buffer.toString());return;
        }
        for (int i = 0; i <arr.size() ; i++) {
            char c=arr.get(i);
            arr.remove(i);
            buffer.append(c);
            Compose(arr,buffer,len,index +1);
            buffer.deleteCharAt(buffer.length() -1); //fixme 删掉最后一位
            arr.add(i,c);
        }
    }

    public static void main(String[] args) {
        Q27_1_Permutation permutation= new Q27_1_Permutation();
        System.out.println(permutation.Permutation("abc").toString());
    }

}
